from math import inf
from copy import deepcopy

def floyd_single(distances,mid,path):
    n=len(distances)
    for i in range(n):
        for j in range(n):
            distance=distances[i][mid]+distances[mid][j]
            if distance < distances[i][j]:
                distances[i][j]=distance
                path[i][j]=mid

def floyd(graph):
    distances=deepcopy(graph)
    n=len(graph)
    path=[ [None]*n for i in range(n) ]
    for i in range(n):
        floyd_single(distances,i,path)
    d,p='',''
    for i in range(n):
        d+=f'{distances[i]}\n'
        p+=f'{path[i]}\n'
    return f'distances:\n{d}\npath:\n{p}'

graph=[
    [0,3,inf,5],
    [2,0,inf,4],
    [inf,1,0,inf],
    [inf,inf,2,0]
]
print(floyd(graph))
